package algorithms.sort;

import java.util.Scanner;

/**
 * 堆排序<br>
 *
 * <br>堆（最大堆）的定义：当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。<br>
 *
 * <br>特点：<br>
 * 1 一棵大小为N的完全二叉树的高度为 大于等于lgN <br>
 * 2 如果父结点下标为k,父元素为a[k]，则子结点为a[2k],a[2k+1]<br>
 *
 * <br>构造堆的算法思想：<br>
 * 1 用长度为N+1的数组pq[]表示一个大小为N的堆，我们不会使用pq[0]，堆元素放在pq[1]..pq[N]<br>
 * 2 堆的有序化：堆的操作首先会进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。<br>
 * 3 在堆的有序化过程中，当某个结点的优先级上升（或是在堆底加入一个新的元素），我们需要由下至上恢复堆的顺序
 *   当某个结点的优先级下降（例如，将根结点替换为一个较小的元素时），我们需要由上至下恢复堆的顺序<br>
 *
 * <br>复杂度：<br>
 * 需要少于（2NlgN+2N）次比较（以及一半次数的交换）
 *
 */
public class HeapSort {

	public static void sort(Comparable[] a){
		int N = a.length - 1;
		//构造最大堆
		//用下沉操作由N个元素构造堆，只需要少于2N次比较以及少于N次交换
		for(int k = N/2; k >= 1; k--)
            sink(a, k, N);

		//进行排序
		while(N > 1){
			exch(a, 1, N--);	//将第最大的元素与数组最后一个元素交换，然后总数减1
			sink(a, 1, N);		//再重新下沉一次，使之称为堆有序
		}
	}
	
	
	private static void sink(Comparable[] a, int k, int N){
		while(2*k <= N){
			int j = 2*k;
			if(j < N && less(a[j], a[j+1])) j++;
			if(!less(a[k], a[j]))	break;
			exch(a, k, j);
			k = j;
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	public static void show(Comparable[] a){
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String raw = scanner.nextLine();
        String[] s1 = raw.split("\\s");
        String[] s2 = new String[s1.length + 1];
        System.arraycopy(s1, 0, s2, 1, s1.length);

        HeapSort.sort(s2);
        HeapSort.show(s2);

        scanner.close();
    }
}
